package org.example.linkedList;

/**
 * @Auther: wangbw
 * @Date:2020/12/1
 * @Description: org.example.linkedList
 * @version: 1.0
 */
public class MergeOrderLink2 {
    public static void main(String[] args) {
        Node head1 = Node.createNode("1", "5", "9");
        Node head2 = Node.createNode("2", "8", "11", "13", "15");
        Node.print(head1);
        Node.print(head2);
        //---------
        Node head = mergeOrderLink(head1, head2);
        Node.print(head);
    }

    //1-5-9
    //2-8-11-13
    private static Node mergeOrderLink2(Node head1, Node head2) {
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }
        Node head = Integer.parseInt(head1.data) <= Integer.parseInt(head2.data) ? head1 : head2;
        Node cur1 = head == head1 ? head1 : head2;
        Node cur2 = head == head1 ? head2 : head1;
        Node next = null;
        Node pre = null;
        while (cur1 != null && cur2 != null) {
            if (Integer.parseInt(cur1.getData()) <= Integer.parseInt(cur2.getData())) {
                pre = cur1;
                cur1 = cur1.next;
            } else {
                next = cur2.next;
                pre.next = cur2;
                pre = cur2;
                cur2.next = cur1;
                cur2 = next;
            }
        }
        pre.next = cur1 == null ? cur2 : cur1;
        return head;
    }

    //1-5-9
    //2-8-11-13
    private static Node mergeOrderLink(Node head1, Node head2) {
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }
        Node head = null;
        if (Integer.parseInt(head1.data) <= Integer.parseInt(head2.data)){
            head = head1;
            head.setNext(mergeOrderLink(head1.getNext(), head2));
        }else{
            head = head2;
            head.setNext(mergeOrderLink(head1, head2.getNext()));
        }
        return head;
    }
}
